/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode LTNode;    
struct ListNode* partition(struct ListNode* head, int x) {
    LTNode* dummy = (LTNode*)malloc(sizeof(LTNode));
    dummy->val = 0;
    dummy->next = head;

    LTNode* pre = dummy;
    LTNode* cur = dummy->next;
    LTNode* big = NULL;
    LTNode* new = NULL;
    int fbig = 1;
    LTNode* btail = NULL;
    while (cur)
    {
        if (cur->val < x)
        {
            if (big == NULL)
            {
                pre = cur;
                cur = cur->next;
            }
            else
            {
                new = cur->next;
                pre->next = cur;
                cur->next = big;
                btail->next = new;
                pre = cur;
                cur  = new;
            }

        }
        else
        {
            if (fbig)
            {
                big = cur;
                fbig = 0;
            }
            btail = cur;
            cur = cur->next;
        }
    }
    return dummy->next;
}